저으 타임라인이 영 썰렁해서 아침에 밀어내기 찬스로 대충 슥삭 써봅니다. 저는 살아있습니다.
해싱, map을 통상 O(1)이라고 가르치는데 수학적인 논리로 맞다면 맞지만 그렇다고 이거슬 O(1)이라고 부른다면 거시기한 것이 사실 거시한것이다. 해시 키를 계산하는데 돈이 들고, 버킷을 나누는데 비용이 든다. 쫑(컬리젼)없는 완전 해시를 말하자면 역시 거시기하므로 우리는 이제 버킷 내부를 탐색해야 하는데 rbtree 같은 걸로 찾아들어가는데 O(nlogn) 같은 비용이 다시 들 것이다. 사실은 많이 사용하는 패턴을 넘어선 용량의 버킷 규모가 되면 재구축한다고 비용이 더 들 것이다. 파이썬 빼고 요즘 많이 쓰는 고성능 언어들이 제공하는 원단 자료구조를 쓰는 것은 대부분 괜찮다고 한다. 성능 잘 나올 것이다. 파이썬은 빼자 ㅠ.ㅠ. 그건 그렇고.
완전 해시라면 32비트 키라 치고 32비트 만큼의 주소 공간을 할당한 배열에 의한 해시가 될 것이다. 소시적 RTOS나 커널 공부할때 MMU 트릭으로 이런 해시 뭘 어째볼까 고민한 사람 많을 것이다. 대부분의 공간은 낭비가 될 뿐만 아니라 주소공간도 낭비고 메모리도 낭비고 그만 합시다..
어쨌거나 성능이 최우선 과제라면 여전히 배열에 의한 해싱의 가능성은 남아있다. 32비트는 4기가니까 빡시고 24비트면 16메가니까 24비트정도면 용처에 따라서는 리즈너블하다. 24비트 짜리 배열에 포인터들을 담아두면 거의 레알에 가까운 O(1)이 될 것이다. 사실 배열이 너무 크면 그거대로 문제인 것이 메모리 잡아 먹는 건 당연한 것이지만 전역이나 정적이라면 바이너리 로딩할때 0으로 지운다고 시간쓰고, 힙이라면 memset 한다고 시간쓴다. 수십메가라면 괜찮은데 수기가라면 티난다.
이렇게 벡터로 유지하는 자료구조는 습관적으로 트리탐색보다는 벡터에 의한 뺑뺑이 순차 탐색을 선호하게 되는데 대부분 괜찮다. 트리보다 수십 수백배 더 많이 일하지만 캐시가 잘 들어맞고, SIMD를 쓰기 좋고, 페이지 테이블을 돌아다닐 확률이 적고, 파이프 스톨을 회피하기 좋고, FPU나 SIMD를 같이 쓰면 각자의 파이프를 쓰는 장점이 있다. NUMA라면 자기 메모리 것을 가져올 확률이 높을 것이다. 그래서 생각보다 수십 수백배 빠른 경우가 많다. 왜때문에 이게 더 빠르지?? 하면 학부때 컴퓨터 아키텍쳐 수업시간에 졸은 것이다. 물론 저는 기계과입니다만.
이제 일합시다.